/**
 * 最小生成树 Kruskal 算法
*/

#ifndef MGRAPH_KRUSKAL
#define MGRAPH_KRUSKAL

#include "MGraph.c"

#include "Set.c"

// 使用堆来存边信息
#define HeapElementType Edge
#include "Heap.c"

int checkCycle(SetType vSet, int v1, int v2) { 
    /* 检查连接V1和V2的边是否在现有的最小生成树子集中构成回路 */
    int root1 = findSet(vSet, v1); /* 得到V1所属的连通集名称 */
    int root2 = findSet(vSet, v2); /* 得到V2所属的连通集名称 */
    if (root1 == root2) {
         /* 若V1和V2已经连通，则该边不能要 */
        return 0;
    } else { 
        /* 否则该边可以被收集，同时将V1和V2并入同一连通集 */
        unionSet(vSet, root1, root2);
        return 1;
    }
}

int edgeComparator(Edge e1, Edge e2) {
    if (e1.weight > e2.weight) {
        return -1;
    } else if (e1.weight < e2.weight) {
        return 1;
    }
    return 0;
}

// 把图的边构建为堆
Heap *buildEdgeHeap(MGraph* graph) {
    Edge* es = calloc(graph->edgeNum, sizeof(Edge));
    int eidx = 0;
    for (int v = 0; v < graph->vertexNum; v++) {
        for (int w = v+1; w < graph->vertexNum; w++) {
            if (isConnection(graph, v, w)) {
                es[eidx++] = createEdge(v, w, graph->g[v][w]);
            }
        }
    }
    Heap* heap = createHeapFromData(es, graph->edgeNum, graph->edgeNum, edgeComparator);
    return heap;
}

// Heap *buildEdgeHeap(MGraph* graph) {
//     Heap* heap = createHeap(graph->edgeNum, edgeComparator);
//     for (int v = 0; v < graph->vertexNum; v++) {
//         for (int w = v+1; w < graph->vertexNum; w++) {
//             if (isConnection(graph, v, w)) {
//                 Edge e = createEdge(v, w, graph->g[v][w]);
//                 insertHeap(heap, e);
//             }
//         }
//     }
//     return heap;
// }

/* 将最小生成树保存为邻接表存储的图MST，返回最小权重和 */
WeightType Kruskal(MGraph* graph, MGraph* MST) {
    // 权重和
    WeightType totalWeight = 0;
    // 收录的边数
    int edgeCount = 0; 
    // 边权重小顶堆
    Heap* edgeHeap = buildEdgeHeap(graph);
    // 顶点集合
    SetType vertexSet = createSet(graph->vertexNum);
    while (edgeCount < graph->vertexNum-1 && !isEmptyHeap(edgeHeap)) {
        // 获取权重最小的边
        Edge e = deleteHeap(edgeHeap);
        // printf("next edge: %d-%d %d\n", e.v, e.w, e.weight);
        // 如果该边的加入不构成回路，即两端结点不属于同一连通集
        if (checkCycle(vertexSet, e.v, e.w)) {
            /* 将该边插入MST */
            insertEdge(MST, e.v, e.w, e.weight);
            totalWeight += e.weight;
            edgeCount++;
        }
    }
    if (edgeCount < graph->vertexNum-1) {
        // 设置错误标记，表示生成树不存在
        totalWeight = -1;
    }
    freeSet(vertexSet);
    freeHeap(edgeHeap);
    return totalWeight;
}

#endif
